\section{Diameter-based objective}
\label{sec:theory2}
In this section, we mention theoretical results for {\it Diameter-sTF} and {\it Diameter-mTF}. We show that these problems are NP-hard (note that the NP-hardness of {\it Diameter-sTF} does not follow from any previous work). We further present an algorithm {\it MinDiameter} (Algorithm ~\ref{algo:minDia})  which is an extension of {\it RarestFirst} in~\cite{LLT}, and prove that it achieves a 2-approximation factor.
%Note that the NP-hardness of {\it Diameter-sTF} does not follow from any previous work. However, due to space constraints the proofs are omitted in this draft.

\begin{algorithm}[]\label{algo:minDia}
\caption{MinDiameter(G, {\cal T})} 
\label{algo:minDia}
\begin{algorithmic}[1]
\FOR{each $<a, k> \in T$}
\STATE $S(a) = \{ i \mid a \in X_i \}$
\ENDFOR
\STATE $a_{rare} = \arg \min_{<a, k>\ \in T} |S(a)|$
\FOR{each $i \in S(a_{rare})$}
\FOR{each $<a, k>\ \in T$}
\STATE $R_{ia} = d_k(i, S(a), k)$
\ENDFOR
\STATE $R_i \leftarrow \max_a R_{ia}$
\ENDFOR
\STATE $i^* \leftarrow \arg \min R_i$
\STATE ${\cal X'} = \{ i^* \}$
\FOR{each $<a, k>\ \in T$}
\STATE ${\cal X'} = {\cal X'} \cup \{  Path_k(i^*, S(a), k) \}$
\ENDFOR
\end{algorithmic}
\end{algorithm}

\begin{claim} 
{\it Diameter-sTF} and {\it Diameter-mTF} problems are NP-complete.
\end{claim}
\begin{proof}
The problem {\it Diameter-sTF} is in NP. We prove that it is NP-hard by reduction from the 3-satisfiability problem. Consider a 3-SAT instance, say $\phi = C_1 \wedge C_2 ... \wedge C_m$, where each clause, $C_j = x \vee y \vee z$, and $\lbrace x, y, z \rbrace \in U = \lbrace u_1, \neg u_1, u_2, \neg u_2, \cdot \cdot \cdot, u_n, \neg u_n \rbrace$. Let, $C = \lbrace  C_1, C_2, \cdot \cdot \cdot, C_m \rbrace$. We construct an instance of {\it Diameter-sTF} problem corresponding to the 3-SAT instance $\phi$.

For each $u_i, \neg u_i \in U$, create two corresponding nodes in $G$. For each clause $C_j = x \vee y \vee z$, create five nodes in $G$, say $C_{j1}, C_{j2}, Cx_{j}, Cy_{j}, Cz_{j} $.

\noindent{\it Rule $1$:} For each $u_i$ and $\neg u_i$, set $w(u_i, \neg u_i)$ = 3.

\noindent{\it Rule $2$:} For each clause $C_j = x \vee y \vee z$,  set\\ 
$w(C_{jt}, p)=1$, $w(C_{jt}, \neg p)=2$ $\forall t\in\{1, 2\}$ and $p\in\{x, y, z\}$. \\
%$w(C_{j1}, x) =  w(C_{j1}, y) = w(C_{j1}, z) = 1$ \\
%$w(C_{j2}, x) =  w(C_{j2}, y) = w(C_{j2}, z) = 1$ \\
%$w(C_{j1}, \neg x) = w(C_{j1}, \neg y) = w(C_{j1}, \neg z) = 2$. \\
%$w(C_{j2}, \neg x) = w(C_{j2}, \neg y) = w(C_{j2}, \neg z) = 2$. \\
$w(Cp_{j}, p) = w(Cp_{j}, \neg q) = 1$ $\forall p, q\in\{x, y, z\}$ and $q\neq p$.
%$w(Cx_{j}, x) = (Cx_{j}, \neg y) = w(Cx_{j}, \neg z) = 1$ \\
%$w(Cy_{j}, y) = (Cy_{j}, \neg x) = w(Cy_{j}, \neg z) = 1$ \\
%$w(Cz_{j}, z) = (Cz_{j}, \neg x) = w(Cz_{j}, \neg y) = 1$

\noindent{\it Rule $3$:} For each pair of nodes $(x, y)$ in $G$ such that if $w(x,y)$ is not set either by {\it Rule $1$} or {\it Rule $2$} then set $w(x, y) = 2$ except in the following two cases.
\begin{enumerate}
\item$x\in U$ and $y\in U$, and any pair of variables from $\lbrace x, y, \neg x, \neg y \rbrace$ appear together in some clause $C_j \in C$.
\item $x, y$ correspond to $C_{j1}, C_{j2}$ for some clause $C_j \in C$.
\end{enumerate}
For each $u_i, \neg u_i \in U$, associate a skill $a$ to node $u_i, \neg u_i$. And for each $C_j \in C$, associate a skill $a$ to the nodes $C_{j1}, C_{j2}$. Now, set  $k =  \#variables + 2 \#clauses = n + 2m$.

We claim that $\phi$ has a satisfying assignment iff $G$ has a sub-graph $\cal X'$ with $|{\cal X'} \cap S(a)| \ge k$ and $diameter({\cal X'}) \le 2$. 

The {\it Diameter-sTF} returns a sub-graph $\cal X'$ with minimum diameter and has at least $k$ nodes with skill $a$. If $diameter({\cal X'}) \le 2$ then it contains either $u_i$ or $\neg u_i$ but not both because $d(u_i, \neg u_i) = 3$. Since $k = n + 2m$, for each variable $u_i \in U$, $\cal X'$ contains node corresponding to either $u_i$ or $\neg u_i$ (not both) and for each clause $C_j \in C$, $\cal X'$ contains nodes corresponding to $C_{j1}$ and $C_{j2}$. Now, since $diameter({\cal X'}) \le 2$, it implies that $d(C_{j1}, C_{j2}) \le 2$. Further, if $C_j = x \vee y \vee z$,  because of the way $G$ is constructed:\\
$d(C_{j1}, C_{j2})  =  d(C_{j1}, x) + d(x, C_{j2})$  \\
$= d(C_{j1}, y) + d(y, C_{j2}) = d(C_{j1}, z) + d(z, C_{j2})= 2$.

This implies that at least one of the nodes corresponding to $x, y, z$ in $C_j$ is included in the sub-graph $\cal X'$. 

If we set the corresponding variable(s) in the each clause to $1$, each clause has a satisfying assignment. Therefore, $\phi$ has a satisfying assignment.

Now, assume that $\phi$ has a satisfying assignment, then either $u_i$ or $\neg u_i$ appears in the assignment. Further, for each clause $C_j = x \vee y \vee z$, at least one of the variables is set to $1$. Then $G$ contains a subgraph $\cal X'$ corresponding to the variables such that $\cal X'$ contains $u_i$ or $\neg u_i$ and $C_{j1}, C_{j2}$. Thus, if $\phi$ has a satisfying assignment then {Diameter-sTF} returns the subgraph $\cal X'$ with $diameter({\cal X'}) \le 2$ and $|{\cal X'} \cap S(a)| = k$. 
This completes the proof. The NP-completeness of {\it Diameter-mTF} follows from {\it Diameter-sTF}. 
\end{proof}


\begin{claim}
For any graph distance function $d$ that satisfies the triangle inequality, the algorithm {\it MinDiameter} achieves an approximation factor of $2$ for the {\it Diameter-sTF} and\\
{\it Diameter-mTF} problems.
\end{claim}
\begin{proof}
The analysis we present here is similar to the analysis of the {\it RarestFirst} algorithm presented in ~\cite{LLT}. First, consider the solution $\cal X'$ output by the {\it MinDiameter} algorithm, and let $a_{rare} \in T$ be the skill possessed by the least number of individuals in $\cal X$. Also, let $i^*$ be the individual picked from set $S(a_{rare})$ to be included in the solution $\cal X'$. Now, consider two other skills $a_1 \ne a_2 \ne a_{rare}$ and individuals $i, i' \in \cal X$ such that $i \in S(a_1), i \not \in S(a_2)$ and $i' \not \in S(a_1), i' \in S(a_2)$. If $i, i'$ are part of the team reported by the {\it MinDiameter} algorithm, it means that $d(i^*, i) \le d_k(i^*, S(a_1), k_1)$ and $d(i^*, i') \le d_k(i^*, S(a_2), k_2)$. Due to the way the algorithm operates, we can lowerbound the Cc-R cost of the optimal solution, $\cal X^*$,  as follows: 

\begin{equation}\label{DiaBounds}
d(i^*, i) \le \mbox{Cc-R}({\cal X^*}) \mbox{ and }  d(i^*, i') \le \mbox{Cc-R}({\cal X^*})
\end{equation}
Since we have assumed that the distance function $d$ satisfies the triangle inequality, \\
$d (i, i') \le d(i, i^*) + d(i^*, i')$\\
By applying the bounds given in ~\eqref{DiaBounds}, we get the proposed approximation factor. \\
$d (i, i') \le$ Cc-R($\cal X^*) +$ Cc-R(${\cal X^*}) \le 2 \cdot $Cc-R($\cal X^*$).
\end{proof}

%The algorithm {\it MinDiameter} generalizes the algorithm {\it RarestFirst} described in ~\cite{LLT}. 
Algorithm {\it MinDiameter} is as follows. For each individual, say $i_r \in S(a_{rare})$ where $a_{rare}$ is the rarest skill (the skill with the minimum size support set $S$), and for each skill $a_i \in {\cal T}$, the algorithm finds the distance to all the nodes in the support set $S(a_i)$. Then, for each support set $S(a_i)$, it chooses the $k_i$-size subset of $S(a_i)$ such that the maximum shortest path distance between $i_r$ and the nodes in this subset is minimum among all $k_i$-size subsets of $S(a_i)$. We call this distance as $k_i$-th shortest distance between $i_r$ and $S(a_i)$ and denote it as $d_k(i_r, S(a_i), k_i)$. Further, we denote the set of $k_i$ shortest paths between $i_r$ and each of the nodes belonging to the corresponding $k_i$-size subset of $S(a_i)$ as $Path_k(i_r, S(a_i), k_i)$. Thus, for each $i_r \in S(a_{rare})$ the algorithm has identified $k_i$ nodes of skill $a_i$, thereby forming a possible solution team that satisfies the constraints. Finally, the algorithm then picks one of these solutions that has minimum diameter. 
%The algorithm is presented below in detail. 
The time complexity of the algorithm {\it MinDiameter}, assuming that all pairs shortest paths are pre-computed, is $O(n^2)$.

